n=100;
m=2000;
road=[|81,2|
2,30|
30,11|
11,26|
26,63|
63,92|
92,42|
42,36|
36,67|
67,46|
46,82|
82,80|
80,73|
73,70|
70,65|
65,51|
51,84|
84,21|
21,97|
97,29|
29,24|
15,25|
25,66|
66,49|
49,96|
96,16|
16,1|
1,9|
9,18|
18,7|
7,100|
100,43|
43,27|
27,50|
50,86|
86,69|
69,22|
22,77|
77,87|
87,39|
39,90|
90,6|
6,17|
17,53|
53,93|
93,48|
48,72|
72,3|
3,95|
95,8|
8,59|
59,45|
45,12|
12,75|
75,40|
40,33|
33,78|
78,79|
79,34|
34,41|
41,83|
83,76|
76,37|
37,98|
98,14|
14,19|
19,74|
74,68|
68,85|
85,28|
28,52|
52,62|
62,71|
71,60|
60,91|
91,64|
64,10|
10,47|
47,54|
54,58|
58,44|
44,56|
56,5|
5,23|
23,55|
55,61|
61,89|
89,94|
94,88|
88,32|
32,20|
20,57|
57,99|
99,13|
13,31|
31,4|
4,35|
81,38|
2,38|
30,38|
11,38|
26,38|
63,38|
92,38|
42,38|
36,38|
67,38|
46,38|
82,38|
80,38|
73,38|
70,38|
65,38|
51,38|
84,38|
21,38|
97,38|
29,38|
24,38|
72,95|
2,41|
86,2|
67,46|
67,80|
65,85|
100,65|
26,97|
74,79|
60,86|
2,47|
78,2|
59,18|
70,68|
28,70|
34,43|
36,63|
92,67|
21,45|
20,21|
65,82|
19,69|
54,37|
67,6|
18,67|
1,17|
63,59|
14,63|
92,21|
36,21|
78,37|
8,49|
71,78|
40,9|
18,9|
100,69|
67,43|
99,67|
68,76|
34,93|
30,70|
89,59|
61,39|
46,66|
74,46|
10,79|
26,29|
75,1|
55,69|
67,36|
36,8|
40,36|
46,24|
4,43|
94,16|
43,52|
27,12|
63,88|
47,63|
64,34|
68,77|
92,57|
52,92|
7,72|
72,48|
74,86|
93,52|
81,65|
6,69|
6,69|
50,83|
77,78|
21,92|
67,47|
48,67|
21,70|
15,95|
34,14|
80,34|
61,80|
80,19|
90,80|
26,62|
49,26|
59,27|
94,96|
45,22|
21,73|
65,3|
15,65|
19,8|
37,74|
73,14|
37,73|
67,29|
56,48|
92,42|
41,93|
30,9|
86,30|
59,98|
43,18|
96,7|
8,16|
24,95|
13,24|
84,3|
14,84|
54,87|
92,30|
99,3|
73,30|
80,19|
86,80|
26,94|
76,26|
39,49|
91,37|
27,83|
17,1|
42,26|
39,68|
92,2|
94,96|
73,33|
32,73|
17,3|
81,85|
48,81|
12,40|
36,84|
72,17|
21,39|
49,21|
96,39|
21,84|
15,43|
79,95|
80,59|
75,80|
10,90|
42,19|
28,42|
16,15|
26,51|
45,12|
65,18|
33,65|
40,8|
44,79|
84,38|
36,84|
43,14|
77,28|
53,50|
19,86|
48,59|
63,57|
93,63|
22,19|
73,82|
99,66|
89,79|
24,74|
62,24|
99,49|
59,17|
96,33|
12,12|
94,34|
55,100|
13,48|
80,73|
82,48|
16,82|
54,19|
73,23|
49,73|
93,59|
43,9|
46,61|
88,46|
61,33|
66,25|
65,82|
62,79|
94,34|
67,22|
55,67|
21,77|
100,21|
51,56|
19,51|
63,61|
52,63|
4,49|
86,28|
97,8|
56,97|
66,40|
70,70|
30,85|
3,30|
19,37|
85,59|
46,28|
27,46|
2,68|
55,2|
26,54|
78,26|
86,68|
33,8|
47,12|
93,74|
84,24|
90,39|
24,81|
88,50|
47,3|
71,98|
51,10|
27,51|
95,85|
78,74|
80,65|
26,74|
90,26|
84,21|
12,45|
67,96|
95,67|
40,83|
95,14|
73,30|
65,73|
66,34|
69,87|
67,64|
22,67|
37,95|
63,100|
79,63|
21,67|
92,11|
97,11|
36,32|
40,36|
97,92|
72,77|
83,74|
72,19|
73,94|
69,73|
73,36|
51,66|
49,51|
15,39|
92,62|
91,92|
76,69|
29,29|
25,45|
64,95|
89,78|
67,100|
95,67|
84,36|
25,9|
61,43|
80,81|
21,81|
1,69|
40,53|
76,79|
73,73|
33,34|
90,3|
32,14|
69,12|
84,79|
96,84|
62,14|
33,40|
63,11|
23,3|
26,64|
43,26|
93,77|
26,67|
95,76|
7,69|
10,18|
36,65|
78,86|
85,76|
63,45|
9,63|
24,92|
82,73|
80,36|
78,49|
30,80|
18,69|
11,71|
4,11|
81,46|
31,14|
83,77|
36,30|
7,19|
14,48|
78,7|
82,51|
70,52|
48,70|
58,15|
80,93|
8,80|
82,85|
3,82|
86,28|
100,8|
26,63|
11,40|
47,11|
40,95|
69,45|
68,41|
40,87|
97,65|
90,69|
41,100|
72,1|
97,20|
61,97|
36,36|
25,72|
100,9|
26,52|
18,26|
79,79|
97,84|
52,14|
16,90|
37,17|
92,74|
76,92|
70,9|
34,70|
73,46|
50,59|
76,96|
63,20|
85,63|
39,85|
75,74|
86,93|
75,16|
13,95|
77,86|
60,69|
61,95|
28,7|
44,68|
47,93|
11,25|
76,11|
40,39|
28,8|
57,53|
26,66|
68,26|
43,28|
80,81|
62,6|
16,6|
90,96|
97,7|
86,97|
31,39|
80,73|
23,1|
87,85|
81,31|
16,81|
6,75|
96,96|
45,77|
30,70|
26,3|
99,26|
96,52|
80,84|
57,37|
75,95|
90,86|
81,6|
48,81|
20,39|
59,48|
11,31|
78,11|
49,45|
73,97|
93,34|
76,18|
97,67|
33,86|
25,79|
91,8|
73,51|
89,66|
80,67|
17,28|
13,66|
85,93|
69,28|
73,29|
4,7|
73,11|
11,15|
33,11|
87,49|
6,1|
89,78|
20,40|
81,68|
95,81|
42,76|
19,42|
31,98|
84,38|
63,28|
39,63|
16,39|
70,67|
39,86|
55,49|
10,76|
73,84|
69,27|
80,28|
6,80|
11,2|
62,68|
97,82|
45,68|
29,42|
72,90|
10,68|
11,32|
75,11|
78,43|
72,1|
43,75|
94,22|
26,48|
45,26|
21,10|
8,21|
26,49|
52,26|
8,72|
4,96|
73,26|
78,62|
71,25|
94,72|
10,68|
59,90|
52,37|
97,83|
61,97|
11,44|
89,11|
63,16|
44,63|
9,78|
73,84|
87,90|
24,29|
65,84|
66,66|
1,16|
29,65|
11,36|
4,96|
16,100|
42,65|
78,93|
14,90|
60,53|
8,86|
72,87|
46,68|
72,46|
70,43|
76,70|
47,95|
84,63|
65,92|
69,25|
40,96|
65,68|
74,65|
91,93|
97,33|
33,97|
51,74|
77,51|
70,21|
46,38|
51,32|
41,51|
81,46|
3,28|
88,66|
99,96|
92,38|
1,16|
84,69|
1,84|
42,83|
79,42|
46,68|
20,46|
46,52|
78,46|
29,24|
8,8|
97,30|
51,57|
28,51|
6,18|
31,14|
93,96|
2,50|
23,2|
21,47|
34,21|
74,8|
25,86|
83,90|
90,40|
29,15|
90,29|
84,11|
21,67|
41,34|
4,59|
8,83|
18,50|
46,50|
77,46|
63,63|
82,80|
1,37|
94,37|
69,52|
40,40|
10,76|
18,78|
11,29|
79,6|
2,27|
91,2|
86,48|
49,1|
74,48|
51,29|
93,50|
21,30|
9,69|
77,85|
81,54|
4,81|
26,28|
66,26|
76,8|
63,52|
89,63|
8,27|
92,46|
51,4|
20,51|
72,12|
62,22|
59,12|
81,70|
48,90|
51,92|
29,14|
79,29|
9,68|
46,46|
82,36|
79,27|
53,19|
45,15|
63,95|
55,63|
42,48|
90,42|
31,3|
90,8|
30,34|
60,30|
79,9|
24,80|
46,3|
89,46|
97,80|
29,81|
61,19|
62,98|
80,35|
99,80|
3,52|
1,3|
9,17|
4,93|
24,30|
59,27|
81,6|
31,81|
13,43|
72,74|
54,19|
9,7|
64,15|
70,81|
21,8|
79,21|
84,2|
86,86|
96,8|
29,79|
54,29|
34,28|
36,42|
65,85|
95,65|
73,92|
97,55|
1,97|
28,77|
40,62|
30,59|
25,30|
8,48|
59,43|
34,48|
63,21|
92,51|
65,95|
3,65|
72,59|
59,90|
24,25|
50,24|
63,12|
78,63|
30,38|
41,50|
63,30|
48,52|
28,100|
96,77|
63,42|
63,85|
19,63|
30,32|
86,30|
64,48|
100,74|
2,87|
75,2|
29,18|
7,29|
94,48|
63,73|
36,26|
97,2|
2,81|
61,34|
75,1|
97,77|
44,97|
96,77|
80,72|
22,80|
40,93|
80,11|
61,28|
11,65|
12,66|
40,33|
54,74|
42,24|
46,48|
22,46|
65,33|
95,65|
65,92|
18,15|
61,59|
90,93|
44,14|
29,21|
41,75|
92,2|
58,8|
56,85|
21,97|
37,90|
97,63|
29,8|
22,29|
88,66|
42,46|
80,30|
72,12|
2,84|
66,6|
96,18|
21,51|
81,46|
31,39|
92,3|
25,92|
45,86|
78,50|
56,77|
73,35|
91,73|
18,39|
30,82|
44,50|
29,11|
70,26|
80,68|
10,80|
14,25|
6,40|
88,98|
84,1|
18,84|
73,21|
98,1|
21,92|
71,78|
80,94|
4,80|
67,37|
6,67|
30,53|
89,30|
65,67|
2,95|
18,2|
80,53|
53,80|
27,7|
11,19|
40,11|
1,76|
58,25|
44,28|
97,97|
51,92|
72,28|
61,62|
24,57|
16,24|
67,6|
96,67|
11,4|
22,11|
39,85|
84,10|
56,84|
71,72|
36,3|
5,36|
24,40|
54,24|
4,9|
26,30|
54,75|
43,6|
61,28|
29,93|
22,29|
82,21|
47,74|
67,42|
92,80|
78,59|
60,3|
26,21|
97,7|
39,97|
84,70|
64,90|
85,83|
32,6|
36,93|
94,36|
50,39|
99,37|
51,1|
1,51|
36,35|
79,36|
26,23|
18,26|
56,7|
42,65|
18,6|
87,85|
60,41|
73,2|
80,92|
34,22|
14,78|
13,87|
79,72|
45,18|
27,87|
65,97|
28,17|
29,46|
65,84|
52,1|
43,16|
81,72|
50,81|
12,69|
16,28|
53,62|
67,13|
12,67|
48,9|
26,92|
37,68|
29,51|
55,90|
70,45|
23,70|
93,100|
81,7|
18,81|
50,86|
100,85|
39,15|
65,8|
1,65|
15,8|
91,22|
11,33|
28,11|
65,56|
100,65|
42,88|
39,42|
91,74|
28,95|
20,100|
7,8|
45,53|
56,25|
2,32|
77,2|
86,49|
21,26|
84,20|
87,84|
30,55|
55,30|
11,22|
49,11|
94,59|
11,67|
43,37|
11,96|
98,11|
68,49|
48,53|
86,40|
14,14|
65,26|
24,85|
79,24|
71,12|
70,81|
11,42|
73,8|
78,73|
31,83|
82,2|
5,37|
32,75|
29,67|
84,95|
86,84|
26,98|
83,26|
46,46|
7,14|
97,41|
22,97|
73,11|
2,49|
10,2|
2,51|
69,17|
81,9|
41,81|
13,95|
26,30|
79,77|
7,98|
26,2|
65,22|
68,65|
9,3|
42,88|
62,42|
44,76|
70,61|
3,70|
30,28|
93,30|
82,37|
20,82|
16,98|
14,43|
84,92|
46,71|
9,46|
46,73|
65,81|
26,80|
96,22|
21,26|
95,9|
77,72|
63,50|
9,63|
29,42|
97,35|
64,97|
76,6|
97,63|
21,36|
21,44|
20,21|
14,75|
97,6|
41,97|
60,76|
26,37|
66,26|
16,52|
29,26|
96,68|
92,50|
33,92|
34,75|
70,29|
68,69|
82,37|
90,82|
42,86|
47,42|
51,67|
87,59|
92,6|
4,92|
42,42|
67,72|
12,67|
84,45|
64,84|
65,2|
42,31|
53,42|
36,96|
16,36|
56,15|
19,50|
40,95|
37,100|
34,90|
10,87|
95,18|
78,93|
80,26|
47,1|
77,7|
36,20|
28,36|
34,45|
70,65|
68,28|
97,2|
86,37|
36,9|
45,36|
88,7|
46,36|
11,53|
62,11|
36,45|
9,36|
53,75|
98,68|
70,70|
81,63|
61,14|
42,36|
62,49|
48,17|
63,65|
46,95|
74,46|
67,73|
73,32|
9,73|
46,32|
83,46|
67,81|
54,41|
63,23|
71,63|
45,16|
7,17|
69,49|
53,28|
44,3|
19,79|
13,48|
100,53|
100,49|
92,73|
24,65|
66,78|
68,50|
73,36|
82,92|
80,65|
11,63|
70,11|
59,93|
39,87|
73,42|
96,68|
84,18|
10,84|
24,51|
21,55|
79,21|
84,61|
20,84|
43,77|
24,92|
52,14|
26,77|
58,26|
43,19|
27,90|
43,40|
42,40|
74,42|
25,14|
11,87|
8,11|
6,3|
37,3|
76,95|
97,53|
69,97|
24,100|
25,24|
76,40|
97,18|
15,97|
96,14|
55,19|
76,27|
23,96|
17,100|
26,63|
92,81|
21,36|
89,28|
47,33|
19,27|
92,94|
15,92|
2,30|
97,72|
91,97|
78,3|
39,83|
73,36|
30,37|
34,30|
29,82|
51,10|
49,51|
10,14|
97,80|
1,74|
18,78|
33,1|
73,45|
74,73|
39,50|
97,42|
90,7|
55,85|
4,1|
26,57|
49,26|
100,15|
63,45|
49,63|
46,32|
14,46|
29,100|
45,29|
84,15|
41,84|
11,4|
25,11|
24,51|
22,96|
11,45|
15,11|
92,82|
91,86|
70,21|
65,59|
14,65|
25,25|
26,46|
63,71|
94,63|
3,85|
19,86|
63,81|
96,75|
9,78|
2,1|
61,2|
52,41|
66,75|
25,8|
30,82|
29,12|
88,29|
99,49|
17,3|
81,65|
75,25|
87,75|
26,79|
39,26|
8,27|
46,51|
1,62|
39,98|
90,19|
92,77|
5,92|
20,76|
12,87|
55,90|
65,11|
62,86|
65,18|
89,65|
65,33|
45,65|
65,21|
47,39|
20,7|
2,46|
42,43|
8,42|
97,61|
98,97|
97,27|
19,97|
46,76|
54,46|
67,24|
67,22|
57,67|
23,37|
46,23|
14,46|
81,46|
65,35|
7,65|
72,15|
32,75|
80,82|
81,82|
19,53|
6,3|
53,79|
22,3|
1,69|
7,8|
61,96|
70,75|
19,70|
24,63|
14,49|
15,45|
70,30|
2,80|
76,53|
74,34|
2,18|
5,2|
3,3|
82,69|
32,82|
67,42|
40,69|
30,26|
99,95|
1,96|
94,41|
6,18|
80,66|
99,80|
26,17|
27,26|
84,29|
26,53|
6,26|
92,65|
77,25|
40,7|
11,11|
17,14|
67,66|
74,67|
24,67|
9,69|
24,83|
86,24|
30,26|
69,77|
87,78|
93,49|
92,42|
56,68|
12,37|
19,12|
28,90|
92,22|
6,92|
80,41|
16,80|
21,24|
71,16|
100,86|
7,72|
21,60|
69,21|
84,90|
54,84|
29,14|
12,29|
43,17|
68,50|
62,86|
87,39|
71,85|
4,66|
51,77|
39,51|
6,37|
29,73|
19,75|
2,43|
4,2|
3,72|
29,92|
70,26|
29,87|
47,29|
52,75|
84,49|
55,84|
53,15|
17,95|
95,68|
29,63|
51,46|
97,84|
24,48|
93,24|
39,74|
73,46|
7,12|
70,100|
1,70|
84,21|
70,21|
27,66|
52,8|
42,82|
95,69|
51,80|
44,68|
65,92|
50,69|
66,62|
8,53|
82,67|
60,1|
53,9|
61,93|
15,90|
36,71|
89,36|
58,9|
21,67|
24,18|
33,24|
95,95|
26,51|
19,9|
65,73|
11,78|
93,11|
34,93|
67,37|
78,67|
57,1|
22,68|
78,90|
53,95|
2,29|
2,80|
58,90|
11,48|
93,11|
6,40|
56,77|
76,18|
70,32|
77,70|
92,70|
86,93|
29,2|
12,8|
65,70|
58,62|
20,3|
36,39|
60,36|
20,45|
82,26|
98,25|
97,46|
73,92|
29,13|
1,29|
49,3|
90,52|
33,72|
67,2|
24,88|
47,24|
26,42|
26,84|
21,24|
2,24|
55,50|
31,78|
24,42|
73,53|
10,73|
46,55|
6,46|
65,30|
36,39|
40,36|
97,81|
84,7|
55,84|
22,79|
37,78|
69,66|
42,90|
54,42|
73,34|
7,73|
3,53|
86,41|
70,97|
81,92|
72,18|
57,62|
90,22|
41,86|
59,27|
49,77|
5,7|
34,78|
66,77|
46,97|
36,76|
25,36|
4,86|
100,17|
2,82|
29,42|
22,15|
47,27|
51,70|
60,69|
81,13|
33,81|
30,29|
81,82|
56,9|
51,81|
3,37|
10,100|
93,77|
55,34|
70,27|
16,70|
43,100|
71,14|
86,79|
32,66|
82,21|
89,69|
82,55|
60,82|
45,3|
70,73|
70,80|
5,18|
73,10|
14,73|
14,78|
43,37|
36,24|
65,74|
5,65|
33,49|
31,48|
65,51|
40,53|
26,89|
77,26|
21,58|
37,21|
81,67|
80,15|
91,80|
56,85|
64,41|
25,66|
11,63|
61,17|
46,72|
79,46|
53,19|
24,39|
9,24|
90,77|
14,68|
70,44|
57,70|
27,68|
1,86|
78,50|
30,64|
68,30|
19,1|
1,12|
82,63|
70,6|
9,70|
70,7|
52,70|
67,91|
43,67|
100,37|
73,96|
72,73|
43,15|
42,11|
20,96|
36,89|
99,36|
30,10|
25,30|
93,86|
5,15|
98,52|
82,39|
89,82|
82,82|
74,33|
89,45|
56,14|
20,48|
6,90|
36,42|
63,70|
68,6|
57,93|
14,83|
3,50|
75,96|
73,73|
97,39|
69,97|
22,74|
71,95|
2,83|
55,2|
63,98|
52,63|
30,34|
53,30|
50,76|
72,98|
70,82|
75,76|
41,8|
82,95|
10,82|
70,65|
15,96|
31,39|
31,3|
81,51|
82,85|
22,82|
81,70|
36,23|
91,36|
23,16|
42,82|
20,93|
9,43|
8,25|
100,7|
98,72|
92,21|
97,1|
60,97|
61,8|
84,52|
23,84|
81,73|
44,25|
17,37|
56,86|
26,45|
49,26|
26,65|
18,34|
80,7|
7,80|
1,22|
29,70|
19,15|
43,53|
10,90|
67,95|
47,67|
99,1|
29,67|
89,1|
75,43|
30,63|
92,21|
73,9|
14,73|
33,45|
28,86|
24,30|
40,41|
30,74|
8,30|
24,54|
54,24|
97,41|
34,97|
81,82|
70,78|
31,70|
87,83|
73,5|
13,73|
10,19|
76,100|
82,62|
86,82|
2,30|
1,28|
73,22|
66,73|
59,62|
66,15|
2,73|
57,48|
52,53|
24,21|
66,34|
96,9|
68,3|
13,90|
94,15|
5,15|
83,87|
43,59|
78,15|
90,83|
71,79|
73,92|
57,43|
42,80|
21,30|
78,90|
99,9|
70,67|
82,9|
83,82|
67,2|
51,99|
91,51|
8,53|
84,95|
76,84|
15,86|
13,90|
2,4|
47,2|
11,11|
98,1|
47,1|
57,59|
80,97|
68,12|
74,3|
54,72|
8,40|
2,92|
80,59|
34,80|
4,37|
28,12|
90,98|
11,14|
58,11|
44,93|
40,96|
57,75|
71,66|
24,26|
66,83|
89,15|
65,31|
68,65|
22,86|
79,16|
22,17|
62,33|
36,21|
94,62|
87,37|
29,6|
33,29|
81,97|
34,93|
93,74|
30,97|
37,15|
65,87|
12,65|
81,92|
30,53|
79,30|
74,16|
10,8|
36,55|
86,36|
66,9|
84,51|
12,50|
96,12|
82,86|
5,82|
60,18|
57,83|
63,88|
14,63|
94,22|
50,12|
51,24|
51,42|
42,48|
41,42|
70,73|
71,33|
30,70|
70,5|
79,70|
30,42|
4,68|
28,72|
23,48|
45,8|
29,34|
19,29|
20,43|
90,16|
20,59|
52,28|
29,81|
24,24|
65,3|
91,65|
28,48|
20,15|
20,90|
26,47|
93,26|
36,36|
15,95|
26,42|
73,12|
31,73|
11,24|
24,98|
91,24|
70,81|
67,83|
41,67|
92,70|
97,28|
19,97|
82,73|
2,42|
2,2|
23,33|
24,36|
68,39|
54,28|
51,69|
53,51|
57,49|
30,56|
18,30|
42,51|
6,16|
28,77|
91,48|
3,98|
63,38|
11,20|
49,11|
81,92|
26,31|
41,26|
24,70|
64,95|
71,59|
3,19|
1,69|
92,24|
73,79|
16,73|
82,21|
22,27|
95,28|
19,74|
87,45|
46,70|
17,14|
50,48|
94,95|
52,18|
73,82|
51,96|
55,51|
31,49|
80,18|
10,80|
46,70|
14,9|
77,98|
71,40|
55,27|
30,11|
81,48|
56,81|
81,48|
28,81|
82,42|
1,39|
63,12|
43,63|
74,77|
82,46|
96,33|
46,16|
68,46|
100,53|
84,65|
67,63|
91,28|
9,40|
11,21|
91,75|
51,66|
91,51|
50,43|
65,44|
62,65|
91,3|
11,87|
76,11|
8,19|
95,52|
63,83|
9,63|
75,77|
66,45|
65,42|
24,51|
46,46|
28,22|
65,80|
46,80|
2,73|
94,100|
65,92|
2,40|
100,2|
41,86|
81,68|
54,81|
3,98|
46,9|
20,46|
51,25|
90,51|
83,1|
34,100|
94,98|
55,100|
97,37|
7,97|
47,7|
63,84|
67,32|
66,67|
15,76|
79,62|
93,66|
70,85|
15,70|
95,79|
74,7|];
s=15;
t=35;